package tree.递归;

import po.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * @author songZiHao
 * @version 1.0.0
 * @ClassName N二叉树的右视图199.java
 * @Description TODO https://leetcode-cn.com/problems/binary-tree-right-side-view/
 * @createTime 2021年04月11日 12:06:00
 */
public class N二叉树的右视图199 {
    List<Integer> list = new ArrayList<>();

    public List<Integer> rightSideView(TreeNode root) {
        //recursive(root);
        //类似先序遍历的方式
        dfs(root,0);
        return list;
    }

    private void dfs(TreeNode root,int deep) {
        //结束条件
        if (root==null){
            return;
        }
        if (list.size() == deep) {
            list.add(root.val);
        }
        deep++;
        dfs(root.right,deep);
        dfs(root.left,deep);
    }


    //存在问题：如果右子树的右子树存在，但是右子树的右子树的右子树不存在，但是左子树的右子树的右子树存在，这种情况下应该是存在视图的。不能用递归的方案
    private void recursive(TreeNode root) {
        if (root==null){
            return;
        }
        list.add(root.val);
        if (root.right != null) {
            recursive(root.right);
        } else if (root.left != null) {
            recursive(root.left);
        }
    }
}
